When load balancing among a number of services, it may be desirable to distribute incoming requests to a service currently servicing the fewest number of connections. However, as the number of services and connections per service increase, identifying the service servicing the fewest connections may take more time to compute. This may have the undesirable effect of hampering load balancing performance and the time to respond to a request at exactly the times when the set of services is the largest and/or busiest. Thus it may be a challenge for a load balancing appliance to efficiently identify the service currently servicing the fewest number of connections.